#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
    void recursion(TreeNode * node, int &sum, bool isLeft)
    {
        if(node->left == nullptr && node->right == nullptr)
        {
            if(isLeft)
            {
                sum += node->val;
            }
        }
        else if(node->left != nullptr && node->right != nullptr)
        {
            recursion(node->left, sum, true);
            recursion(node->right, sum, false);
        }
        else if(node->left == nullptr)
        {
            recursion(node->right, sum, false);
        }
        else
        {
            recursion(node->left, sum, true);
        }
        return;
    }

    int sumOfLeftLeaves(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return 0;
        }
        int sum = 0;
        recursion(root, sum, false);
        return sum;
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 404. 左叶子之和 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [3,9,20,null,null,15,7]
    cout << "\n测试案例1: [3,9,20,null,null,15,7]" << endl;
    TreeNode* root1 = createNode(3);
    root1->left = createNode(9);
    root1->right = createNode(20);
    root1->right->left = createNode(15);
    root1->right->right = createNode(7);
    
    int result1 = solution.sumOfLeftLeaves(root1);
    cout << "输入: [3,9,20,null,null,15,7]" << endl;
    cout << "输出: " << result1 << endl;
    cout << "期望: 24 (左叶子节点: 9 + 15 = 24)" << endl;
    
    // 测试案例2: 示例2 - [1]
    cout << "\n测试案例2: [1]" << endl;
    TreeNode* root2 = createNode(1);
    
    int result2 = solution.sumOfLeftLeaves(root2);
    cout << "输入: [1]" << endl;
    cout << "输出: " << result2 << endl;
    cout << "期望: 0 (没有左叶子节点)" << endl;
    
    // 测试案例3: 空树 []
    cout << "\n测试案例3: []" << endl;
    TreeNode* root3 = nullptr;
    
    int result3 = solution.sumOfLeftLeaves(root3);
    cout << "输入: []" << endl;
    cout << "输出: " << result3 << endl;
    cout << "期望: 0" << endl;
    
    // 测试案例4: 完全二叉树 [1,2,3,4,5,6,7]
    cout << "\n测试案例4: [1,2,3,4,5,6,7]" << endl;
    TreeNode* root4 = createNode(1);
    root4->left = createNode(2);
    root4->right = createNode(3);
    root4->left->left = createNode(4);
    root4->left->right = createNode(5);
    root4->right->left = createNode(6);
    root4->right->right = createNode(7);
    
    int result4 = solution.sumOfLeftLeaves(root4);
    cout << "输入: [1,2,3,4,5,6,7]" << endl;
    cout << "输出: " << result4 << endl;
    cout << "期望: 10 (左叶子节点: 4 + 6 = 10)" << endl;
    
    // 测试案例5: 只有左子树 [1,2,null,4]
    cout << "\n测试案例5: [1,2,null,4]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->left->left = createNode(4);
    
    int result5 = solution.sumOfLeftLeaves(root5);
    cout << "输入: [1,2,null,4]" << endl;
    cout << "输出: " << result5 << endl;
    cout << "期望: 4 (左叶子节点: 4)" << endl;
    
    // 测试案例6: 只有右子树 [1,null,3,null,7]
    cout << "\n测试案例6: [1,null,3,null,7]" << endl;
    TreeNode* root6 = createNode(1);
    root6->right = createNode(3);
    root6->right->right = createNode(7);
    
    int result6 = solution.sumOfLeftLeaves(root6);
    cout << "输入: [1,null,3,null,7]" << endl;
    cout << "输出: " << result6 << endl;
    cout << "期望: 0 (没有左叶子节点)" << endl;
    
    // 测试案例7: 混合情况 [1,2,3,4,5,null,8,null,null,6,7]
    cout << "\n测试案例7: [1,2,3,4,5,null,8,null,null,6,7]" << endl;
    TreeNode* root7 = createNode(1);
    root7->left = createNode(2);
    root7->right = createNode(3);
    root7->left->left = createNode(4);
    root7->left->right = createNode(5);
    root7->right->right = createNode(8);
    root7->left->right->left = createNode(6);
    root7->left->right->right = createNode(7);
    
    int result7 = solution.sumOfLeftLeaves(root7);
    cout << "输入: [1,2,3,4,5,null,8,null,null,6,7]" << endl;
    cout << "输出: " << result7 << endl;
    cout << "期望: 10 (左叶子节点: 4 + 6 = 10)" << endl;
    
    // 测试案例8: 对称树 [1,2,2,3,4,4,3]
    cout << "\n测试案例8: [1,2,2,3,4,4,3]" << endl;
    TreeNode* root8 = createNode(1);
    root8->left = createNode(2);
    root8->right = createNode(2);
    root8->left->left = createNode(3);
    root8->left->right = createNode(4);
    root8->right->left = createNode(4);
    root8->right->right = createNode(3);
    
    int result8 = solution.sumOfLeftLeaves(root8);
    cout << "输入: [1,2,2,3,4,4,3]" << endl;
    cout << "输出: " << result8 << endl;
    cout << "期望: 7 (左叶子节点: 3 + 4 = 7)" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    // root3 已经是 nullptr，不需要释放
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    deleteTree(root8);
    
    cout << "\n=== 测试完成 ===" << endl;
    cout << "\n注意：如果输出结果与期望不符，可能是因为Solution中没有检查isLeft参数" << endl;
    cout << "建议在递归函数的叶子节点判断中加入 && isLeft 条件" << endl;
    
    return 0;
}